Maximum swap

Time: O(LogN), Space: O(LogN); medium

Note:

• LogN is the length of the number string

Given a non-negative integer, you could swap two digits at most once to get the maximum valued number. Return the maximum valued number you could get.

Example 1:

Input: num = 2736

Output: 7236

Explanation:

• Swap the number 2 and the number 7.

Example 2:

Input: num = 9973

Output: 9973

Explanation:

• No swap.

Note:

• The given number is in the range [0, 10^8]

class Solution1(object):
    def maximumSwap(self, num):
        """
        :type num: int
        :rtype: int
        """
        digits = list(str(num))
        left, right = 0, 0
        max_idx = len(digits)-1

        for i in reversed(range(len(digits))):
            if digits[i] > digits[max_idx]:
                max_idx = i
            elif digits[max_idx] > digits[i]:
                left, right = i, max_idx

        digits[left], digits[right] = digits[right], digits[left]

        return int("".join(digits))

s = Solution1()
num = 2736
assert s.maximumSwap(num) == 7236
num = 9973
assert s.maximumSwap(num) == 9973

See also:

https://leetcode.com/problems/maximum-swap

https://www.lintcode.com/problem/maximum-swap